/*
@Copyright:LintCode
@Author:   tjyemail
@Problem:  http://www.lintcode.com/problem/triangle
@Language: C++
@Datetime: 16-02-09 05:22
*/

class Solution {
public:
    /**
     * @param triangle: a list of lists of integers.
     * @return: An integer, minimum path sum.
     */
    int minimumTotal(vector<vector<int> > &triangle) {
        // write your code here
        for(int i=triangle.size()-2;i>=0;--i){
            for(int j=0;j<=i;++j){
                triangle[i][j]+=(triangle[i+1][j]<triangle[i+1][j+1]
                    ?triangle[i+1][j]:triangle[i+1][j+1]);
            }
        }
        return triangle[0][0];
    }
};
